#include <stdlib.h>
#include <stdio.h>

// 关键路径
// 适用于有向无环图(DAG)，用于项目管理中的任务调度

typedef char VertexType; // 顶点数据类型
typedef int EdgeType;  // 边的权值类型
#define MAXVEX 100       // 最大顶点数
#define MAX 0x10000   // 无穷大

typedef struct{
    VertexType vexs[MAXVEX];          // 顶点表
    EdgeType arc[MAXVEX][MAXVEX];     // 邻接矩阵
    int numVertexes, numEdges;        // 图的当前顶点数和边数
} Graph;

typedef struct EdgeNode{
    int edge_vex;            // 该边所指向的顶点的位置
    int weight;             // 边的权值
    struct EdgeNode *next;   // 指向下一条边的指针
} EdgeNode;

typedef struct VertexNode{
    VertexType data;         // 顶点信息
    int in;                 // 顶点入度
    EdgeNode *head;     // 指向第一条依附该顶点的边的指针
} VertexNode;

typedef VertexNode AdjList[MAXVEX];

typedef struct{
    AdjList adjList;     // 邻接表
    int numVertexes, numEdges;        // 图的当前顶点数和边数
} GraphAdjList;

typedef GraphAdjList *Adj_List_Graph;

void createGraph(Graph *G){
    G->numVertexes = 10;
    G->numEdges = 13;

    for (int i = 0; i < G->numVertexes; i++){   // 初始化邻接矩阵
        G->vexs[i] = i;
    }
    for (int i = 0; i < G->numVertexes; i++){      // 初始化邻接矩阵
        for (int j = 0; j < G->numVertexes; j++){  // 初始化邻接矩阵
            if (i == j){                  
                G->arc[i][j] = 0;  // 对角线为0
            }
            else {
                G->arc[i][j] = MAX; // 用无穷大表示不连通
            }
        }
    }

    // 建立边
G->arc[0][1] = 3;
G->arc[0][2] = 4;
G->arc[1][3] = 5;
G->arc[1][4] = 6;
G->arc[2][3] = 8;
G->arc[2][5] = 7;
G->arc[3][4] = 3;
G->arc[4][6] = 9;
G->arc[4][7] = 4;
G->arc[5][7] = 6;
G->arc[6][8] = 2;
G->arc[7][9] = 5;
G->arc[8][9] = 3;
}

void createALGraph(Adj_List_Graph *GL, Graph G){
    EdgeNode *e;
    *GL = (Adj_List_Graph)malloc(sizeof(GraphAdjList));
    (*GL)->numVertexes = G.numVertexes;
    (*GL)->numEdges = G.numEdges;
    
    for (int i = 0; i < G.numVertexes; i++){ // 初始化邻接表
        (*GL)->adjList[i].data = G.vexs[i];
        (*GL)->adjList[i].in = 0; // 初始化入度为0
        (*GL)->adjList[i].head = NULL; // 初始化边表为空
    }

    for (int i = 0; i < G.numVertexes; i++){ // 建立边表
        for (int j = 0; j < G.numVertexes; j++){
            if (G.arc[i][j] != 0 && G.arc[i][j] < MAX){ // 有边
                e = (EdgeNode *)malloc(sizeof(EdgeNode)); // 创建边结点
                e->edge_vex = j; // 该边指向的顶点位置
                e->next = (*GL)->adjList[i].head; // 将e指向当前顶点的第一条边
                (*GL)->adjList[i].head = e; // 将当前顶点的第一条边指向e
                (*GL)->adjList[j].in++; // 被指向的顶点入度加1
            }
        }
    }
}

void critical_path(Adj_List_Graph GL){
    EdgeNode *e;
    int top = -1; // 栈顶指针
    int top2 = -1; // 第二个栈顶指针
    int stack[MAXVEX]; // 辅助栈
    int stack2[MAXVEX]; // 第二个辅助栈
    int ve[MAXVEX]; // 事件最早发生时间
    int vl[MAXVEX]; // 事件最迟发生时间
    int curr; // 当前顶点位置
    int k; // 辅助变量

    for (int i = 0; i < MAXVEX; i++) {
        if(GL->adjList[i].in == 0) {
            stack[++top] = i; // 入度为0的顶点入栈
        }
    }

    for(int i = 0; i < GL->numVertexes; i++) {
        ve[i] = 0; // 初始化ve数组
    }

    while(top != -1) { // 栈不为空
        curr = stack[top--]; // 出栈
        printf("V%d -> ",GL->adjList[curr].data); // 输出该顶点

        stack2[++top2] = curr; // 将出栈的顶点压入第二个栈
        e = GL->adjList[curr].head; // 指向当前顶点的第一条边
        while(e) { // 遍历当前顶点的所有边
            k = e->edge_vex; // 该边指向的顶点位置
            GL->adjList[k].in--; // 该顶点入度减1
            if(GL->adjList[k].in == 0) {
                stack[++top] = k; // 入度为0的顶点入栈
            }
            if(ve[curr] + e->weight > ve[k]) { // 更新ve数组
                ve[k] = ve[curr] + e->weight;
            }
            e = e->next; // 指向下一条边
        }
    }
    printf("\n");
    printf("ve: ");

    for(int i = 0; i < GL->numVertexes; i++) {
        printf("%d -> ", ve[i]);
    }
    printf("\n");

    for(int i = 0; i < GL->numVertexes; i++) {
        vl[i] = ve[GL->numVertexes - 1]; // 初始化vl数组
    }

    while(top2 != -1) { // 第二个栈不为空
        curr = stack2[top2--]; // 出栈
        e = GL->adjList[curr].head; // 指向当前顶点的第一条边
        while(e) { // 遍历当前顶点的所有边
            k = e->edge_vex; // 该边指向的顶点位置
            if(vl[k] - e->weight < vl[curr]) { // 更新vl数组
                vl[curr] = vl[k] - e->weight;
            }
            e = e->next; // 指向下一条边
        }
    }
    printf("vl: ");
    for(int i = 0; i < GL->numVertexes; i++) {
        printf("%d -> ", vl[i]);
    }
    printf("\n");

    for(int i = 0;i < GL->numVertexes; i++){
        if(ve[i] == vl[i]){
            printf("V%d -> ", i);
        }
    }
}

int main(){
    Graph G;        
    createGraph(&G);
    Adj_List_Graph GL;
    createALGraph(&GL, G);
    printf("关键路径结果:\n");
    critical_path(GL);
    return 0;
}